import copy


class Solution:
    def solveNQueens(self, n: int):
        tar_list, self.res = [], 0
        for i in range(0, n):
            tar_list.append([])
            for j in range(0, n):
                tar_list[i].append("x")
        self.add_queen(0, n, tar_list)
        return self.res

    def add_queen(self, x, n, list_in):
        if x >= n:
            return True
        for i in range(0, n):
            if list_in[x][i] == "x":
                mid_list = copy.deepcopy(list_in)
                self.check_attack2(x, i, n, mid_list)
                mid_list[x][i] = "Q"
                self.add_queen(x + 1, n, mid_list)
                if x == n-1:
                    self.res += 1

    @staticmethod
    def check_attack(x, i, n, mid_list):
        for count in range(0, n):
            if count != i:
                mid_list[x][count] = "."
            if count != x:
                mid_list[count][i] = "."
            if x + count < n and i + count < n:
                mid_list[x + count][i + count] = "."
            if x + count < n and 0 <= i - count:
                mid_list[x + count][i - count] = "."
            if 0 <= x - count and i + count < n:
                mid_list[x - count][i + count] = "."
            if 0 <= x - count and 0 <= i - count:
                mid_list[x - count][i - count] = "."

    @staticmethod
    def check_attack2(x, i, n, mid_list):
        for count in range(0, n):
            if count != i:
                mid_list[x][count] = "."
            if count != x:
                mid_list[count][i] = "."
            try:
                if 0 <= i-x+count < n:
                    mid_list[count][i-x+count] = "."
            except:
                pass
            try:
                if 0 <= i+x-count < n:
                    mid_list[count][i+x-count] = "."
            except:
                pass


a = Solution()
print(a.solveNQueens(8))
